#include <thrust/host_vector.h>
#include <thrust/device_vector.h>

#include <string>
#include <iostream>
#include <cassert>

#include "cuda_timer.h"
#include "random.h"
#include <unittest/unittest.h>

// Algos
#include "adjacent_difference.h"
#include "binary_search.h"
#include "copy.h"
#include "count.h"
#include "equal.h"
#include "extrema.h"
#include "fill.h"
#include "find.h"
#include "for_each.h"
#include "gather.h"
#include "generate.h"
#include "inner_product.h"
#include "logical.h"
#include "merge.h"
#include "mismatch.h"
#include "partition.h"
#include "reduce.h"
#include "remove.h"
#include "replace.h"
#include "reverse.h"
#include "scan.h"
#include "scatter.h"
#include "sequence.h"
#include "set_operations.h"
#include "sort.h"
#include "swap.h"
#include "transform.h"
#include "transform_reduce.h"
#include "transform_scan.h"
#include "uninitialized_copy.h"
#include "uninitialized_fill.h"
#include "unique.h"

template <typename Vector>
void filter(Vector& times)
{
  // XXX the filter could drop outliers, select the median, etc.

  typedef typename Vector::value_type T;

  T average_time = thrust::reduce(times.begin(), times.end()) / (T) times.size();
  times.resize(1);
  times[0] = average_time;
}

template <typename Test, typename Vector>
void report(Test& test, Vector& times)
{
  std::string test_name = unittest::type_name<Test>();

  if (test_name.find("<") != std::string::npos)
  {
    test_name.resize(test_name.find("<"));
  }

  std::cout << test_name << ", ";
  for (size_t i = 0; i < times.size(); i++)
    std::cout << times[i] << ", ";
  std::cout << "\n";
}


template <typename Test>
void benchmark(Test& test, size_t iterations = 20)
{
  // run one iteration (warm up)
  test();

  test.reset();
  
  thrust::host_vector<double> times(iterations);

  for (size_t i = 0; i < iterations; i++)
  {
    cuda_timer timer;

    test();
    
    times[i] = timer.elapsed();

    test.reset();
  }

  filter(times);

  report(test, times);
};

template <typename T>
struct default_for_each_function
{
  __host__ __device__
  void operator()(T& x)
  {
    x = T();
  }
};

template <typename T>
struct default_generate_function
{
  __host__ __device__
  T operator()(void)
  {
    return T();
  }
};


int main(void)
{
  size_t n = 4 << 20;

  typedef thrust::device_vector<int>     Vector;
  typedef testing::random_integers<int>  RandomIntegers;
  typedef testing::random_integers<bool> RandomBooleans;
  
  RandomIntegers A(n, 123);
  RandomIntegers B(n, 234);
  RandomIntegers C(n, 345);
  RandomBooleans D(n, 456);
  Vector         T(n, 1);
  Vector         F(n, 0);
  Vector         S(n); thrust::sequence(S.begin(), S.end());
  Vector         U(2*n, 0);

  typedef thrust::equal_to<int> E;
  typedef thrust::identity<int> I;
  typedef thrust::less<int>     L;
  typedef thrust::plus<int>     P;
  typedef thrust::negate<int>   N;
  typedef thrust::minus<int>    M;
  typedef Vector                V;
  typedef default_for_each_function<int> X;
  typedef default_generate_function<int> Y;

  { AdjacentDifference<V,V>                           temp(A,B);             benchmark(temp); } // adjacent_difference
  { AdjacentDifferenceBinaryOp<V,V,M>                 temp(A,B,M());         benchmark(temp); }
  { LowerBound<V,V,V>                                 temp(A,B,C);           benchmark(temp); } // binary_search
  { LowerBoundComp<V,V,V,L>                           temp(A,B,C,L());       benchmark(temp); }
  { UpperBound<V,V,V>                                 temp(A,B,C);           benchmark(temp); }
  { UpperBoundComp<V,V,V,L>                           temp(A,B,C,L());       benchmark(temp); }
  { BinarySearch<V,V,V>                               temp(A,B,C);           benchmark(temp); }
  { BinarySearchComp<V,V,V,L>                         temp(A,B,C,L());       benchmark(temp); }
  { Copy<V,V>                                         temp(A,B);             benchmark(temp); } // copy
  { CopyN<V,V>                                        temp(A,B);             benchmark(temp); }
  { CopyIf<V,V,I>                                     temp(D,B,I());         benchmark(temp); }
  { CopyIfStencil<V,V,V,I>                            temp(A,D,B,I());       benchmark(temp); }
  { Count<V,int>                                      temp(D,1);             benchmark(temp); } // count
  { CountIf<V,I>                                      temp(D,I());           benchmark(temp); }
  { Equal<V,V>                                        temp(A,A);             benchmark(temp); } // equal
  { EqualBinaryPred<V,V,E>                            temp(A,A,E());         benchmark(temp); }
  { MinElement<V>                                     temp(A);               benchmark(temp); } // extrema
  { MinElementComp<V,L>                               temp(A,L());           benchmark(temp); }
  { MaxElement<V>                                     temp(A);               benchmark(temp); }
  { MaxElementComp<V,L>                               temp(A,L());           benchmark(temp); }
  { MinMaxElement<V>                                  temp(A);               benchmark(temp); }
  { MinMaxElementComp<V,L>                            temp(A,L());           benchmark(temp); }
  { Fill<V,int>                                       temp(A,0);             benchmark(temp); } // fill
  { FillN<V,int>                                      temp(A,0);             benchmark(temp); }
  { Find<V,int>                                       temp(F,1);             benchmark(temp); } // find
  { FindIf<V,I>                                       temp(F,I());           benchmark(temp); }
  { FindIfNot<V,I>                                    temp(T,I());           benchmark(temp); }
  { ForEach<V,X>                                      temp(A,X());           benchmark(temp); } // for_each
  { Gather<V,V,V>                                     temp(S,A,B);           benchmark(temp); } // gather
  { GatherIf<V,V,V,V>                                 temp(S,D,A,B);         benchmark(temp); }
  { GatherIfPred<V,V,V,V,I>                           temp(S,D,A,B,I());     benchmark(temp); }
  { Generate<V,Y>                                     temp(A,Y());           benchmark(temp); } // generate
  { GenerateN<V,Y>                                    temp(A,Y());           benchmark(temp); }
  { InnerProduct<V,V,int>                             temp(A,B,0);           benchmark(temp); } // inner_product
  { InnerProductBinaryOp<V,V,int,P,E>                 temp(A,B,0,P(),E());   benchmark(temp); }
  { AllOf<V,I>                                        temp(T,I());           benchmark(temp); } // logical
  { AnyOf<V,I>                                        temp(F,I());           benchmark(temp); }
  { NoneOf<V,I>                                       temp(F,I());           benchmark(temp); }
  { Merge<V,V,V>                                      temp(A,B,U);           benchmark(temp); } // merge
  { MergeComp<V,V,V,L>                                temp(A,B,U,L());       benchmark(temp); }
  { Mismatch<V,V>                                     temp(A,A);             benchmark(temp); } // mismatch
  { MismatchBinaryPred<V,V,E>                         temp(A,A,E());         benchmark(temp); }
  { Partition<V,I>                                    temp(D,I());           benchmark(temp); } // partition
  { PartitionCopy<V,V,V,I>                            temp(D,A,B,I());       benchmark(temp); }
  { StablePartition<V,I>                              temp(A,I());           benchmark(temp); }
  { StablePartitionCopy<V,V,V,I>                      temp(D,A,B,I());       benchmark(temp); }
  { IsPartitioned<V,I>                                temp(T,I());           benchmark(temp); }
  { PartitionPoint<V,I>                               temp(T,I());           benchmark(temp); }
  { Reduce<V>                                         temp(A);               benchmark(temp); } // reduce
  { ReduceInit<V,int>                                 temp(A,0);             benchmark(temp); }
  { ReduceInitBinaryOp<V,int,P>                       temp(A,0,P());         benchmark(temp); }
  { ReduceByKey<V,V,V,V>                              temp(D,A,B,C);         benchmark(temp); }
  { ReduceByKeyPred<V,V,V,V,E>                        temp(D,A,B,C,E());     benchmark(temp); }
  { ReduceByKeyPredBinaryOp<V,V,V,V,E,P>              temp(D,A,B,C,E(),P()); benchmark(temp); }
  { Remove<V,int>                                     temp(D,0);             benchmark(temp); } // remove
  { RemoveCopy<V,V,int>                               temp(D,A,0);           benchmark(temp); }
  { RemoveIf<V,I>                                     temp(D,I());           benchmark(temp); }
  { RemoveIfStencil<V,V,I>                            temp(D,A,I());         benchmark(temp); }
  { RemoveCopyIf<V,V,I>                               temp(A,D,I());         benchmark(temp); }
  { RemoveCopyIfStencil<V,V,V,I>                      temp(A,D,B,I());       benchmark(temp); }
  { Replace<V,int>                                    temp(D,0,2);           benchmark(temp); } // replace
  { ReplaceCopy<V,V,int>                              temp(D,A,0,2);         benchmark(temp); }
  { ReplaceIf<V,I,int>                                temp(D,I(),0);         benchmark(temp); }
  { ReplaceIfStencil<V,V,I,int>                       temp(A,D,I(),0);       benchmark(temp); }
  { ReplaceCopyIf<V,V,I,int>                          temp(D,A,I(),0);       benchmark(temp); }
  { ReplaceCopyIfStencil<V,V,V,I,int>                 temp(A,D,B,I(),0);     benchmark(temp); }
  { Reverse<V>                                        temp(A);               benchmark(temp); }
  { ReverseCopy<V,V>                                  temp(A,B);             benchmark(temp); }
  { InclusiveScan<V,V>                                temp(A,B);             benchmark(temp); } // scan
  { InclusiveScanBinaryOp<V,V,P>                      temp(A,B,P());         benchmark(temp); }
  { ExclusiveScan<V,V>                                temp(A,B);             benchmark(temp); }
  { ExclusiveScanInit<V,V,int>                        temp(A,B,0);           benchmark(temp); }
  { ExclusiveScanInitBinaryOp<V,V,int,P>              temp(A,B,0,P());       benchmark(temp); }
  { InclusiveScanByKey<V,V,V>                         temp(D,A,B);           benchmark(temp); }
  { InclusiveScanByKeyPred<V,V,V,E>                   temp(D,A,B,E());       benchmark(temp); }
  { InclusiveScanByKeyPredBinaryOp<V,V,V,E,P>         temp(D,A,B,E(),P());   benchmark(temp); }
  { ExclusiveScanByKey<V,V,V>                         temp(D,A,B);           benchmark(temp); }
  { ExclusiveScanByKeyInit<V,V,V,int>                 temp(D,A,B,0);         benchmark(temp); }
  { ExclusiveScanByKeyInitPred<V,V,V,int,E>           temp(D,A,B,0,E());     benchmark(temp); }
  { ExclusiveScanByKeyInitPredBinaryOp<V,V,V,int,E,P> temp(D,A,B,0,E(),P()); benchmark(temp); }
  { Scatter<V,V,V>                                    temp(A,S,B);           benchmark(temp); } // scatter
  { ScatterIf<V,V,V,V>                                temp(A,S,D,B);         benchmark(temp); }
  { ScatterIfPred<V,V,V,V,I>                          temp(A,S,D,B,I());     benchmark(temp); }
  { Sequence<V>                                       temp(A);               benchmark(temp); } // sequence
  { SequenceInit<V,int>                               temp(A,0);             benchmark(temp); } // sequence
  { SequenceInitStep<V,int>                           temp(A,0,1);           benchmark(temp); } // sequence
  { SetDifference<V,V,V>                              temp(A,B,U);           benchmark(temp); } // set_operations
  { SetDifferenceComp<V,V,V,L>                        temp(A,B,U,L());       benchmark(temp); }
  { SetIntersection<V,V,V>                            temp(A,B,U);           benchmark(temp); }
  { SetIntersectionComp<V,V,V,L>                      temp(A,B,U,L());       benchmark(temp); }
  { SetSymmetricDifference<V,V,V>                     temp(A,B,U);           benchmark(temp); }
  { SetSymmetricDifferenceComp<V,V,V,L>               temp(A,B,U,L());       benchmark(temp); }
  { SetUnion<V,V,V>                                   temp(A,B,U);           benchmark(temp); }
  { SetUnionComp<V,V,V,L>                             temp(A,B,U,L());       benchmark(temp); }
  { Sort<V>                                           temp(A);               benchmark(temp); } // sort
  { SortComp<V,L>                                     temp(A,L());           benchmark(temp); }
  { StableSort<V>                                     temp(A);               benchmark(temp); }
  { StableSortComp<V,L>                               temp(A,L());           benchmark(temp); }
  { SortByKey<V,V>                                    temp(A,B);             benchmark(temp); }
  { SortByKeyComp<V,V,L>                              temp(A,B,L());         benchmark(temp); }
  { StableSortByKey<V,V>                              temp(A,B);             benchmark(temp); }
  { StableSortByKeyComp<V,V,L>                        temp(A,B,L());         benchmark(temp); }
  { IsSorted<V>                                       temp(S);               benchmark(temp); }
  { IsSortedComp<V,L>                                 temp(S,L());           benchmark(temp); }
  { IsSortedUntil<V>                                  temp(S);               benchmark(temp); }
  { IsSortedUntilComp<V,L>                            temp(S,L());           benchmark(temp); }
  { SwapRanges<V,V>                                   temp(A,B);             benchmark(temp); } // swap
  { TransformUnaryOp<V,V,N>                           temp(A,B,N());         benchmark(temp); } // transform
  { TransformIfUnaryOp<V,V,V,N,I>                     temp(A,D,B,N(),I());   benchmark(temp); } // transform
  { TransformBinaryOp<V,V,V,M>                        temp(A,B,C,M());       benchmark(temp); } // transform
  { TransformIfBinaryOp<V,V,V,V,M,I>                  temp(A,B,D,C,M(),I()); benchmark(temp); } // transform
  { TransformReduce<V,N,int,P>                        temp(A,N(),0,P());     benchmark(temp); } // transform_reduce
  { TransformInclusiveScan<V,V,N,P>                   temp(A,B,N(),P());     benchmark(temp); } // transform_scan
  { TransformExclusiveScan<V,V,N,int,P>               temp(A,B,N(),0,P());   benchmark(temp); }
  { UninitializedCopy<V,V>                            temp(A,B);             benchmark(temp); } // uninitialized_copy
  { UninitializedFill<V,int>                          temp(A,0);             benchmark(temp); } // fill
  { UninitializedFillN<V,int>                         temp(A,0);             benchmark(temp); }
  { Unique<V>                                         temp(D);               benchmark(temp); } // unique
  { UniquePred<V,E>                                   temp(D,E());           benchmark(temp); } // unique
  { UniqueCopy<V,V>                                   temp(D,A);             benchmark(temp); }
  { UniqueCopyPred<V,V,E>                             temp(D,A,E());         benchmark(temp); }
  { UniqueByKey<V,V>                                  temp(D,A);             benchmark(temp); }
  { UniqueByKeyPred<V,V,E>                            temp(D,A,E());         benchmark(temp); }
  { UniqueByKeyCopy<V,V,V,V>                          temp(D,A,B,C);         benchmark(temp); }
  { UniqueByKeyCopyPred<V,V,V,V,E>                    temp(D,A,B,C,E());     benchmark(temp); }

  // host<->device copy

  return 0;
}

